Automatic Proofs of Asymptotic ABNORMALITY (and much more!) of Natural Statistics Defined on Catalan-Counted Combinatorial Families

摘要

In this case-study in computer-human collaboration, we develop, implement,and execute symbolic-computational algorithms for the automatic discovery andproof of explicit expressions for the expectation, variance, and higher momentsof a large class of natural combinatorial statistics defined on Catalan-countedobjects, enabling, inter-alia, to prove that they are not asymptoticallynormal. In particular, we reproduce in 0.12 seconds results of Miklos Bona, andderive far deeper results, way beyond the scope of humans, concerning highermoments of the random variable "number of occurrences of a pattern" in the setof 132-avoiding permutations for all patterns of length 2 and 3, and, moreimpressively, explicit expressions for the averages for all patterns of lengthsup to 10. The ample output inspired us to make an intriguing conjectureconcerning the number of so-called Bona classes, and we pledge to donate 100dollars to the OEIS Foundation in honor of the prover (or disprover).